package 二分;
import java.util.Arrays;
import java.util.Comparator;
public class leetcode436真傻逼描述题 {
	/**
	 * 简单翻译 ： 每个区间  有两个数 [A , B]. 找大于 等于 B 的 最小的 A 位置
	 * 
	 * 用的  不是 普通的 二分查找  而是 》= 某个值的 最左边的 下标 
	 * 这种的 二分查找
	 */
	public static void main(String []args) {
		int intervals [][] = {{4,5},{2,3},{1,2}};
		System.out.println(Arrays.toString(solution(intervals)));
	}
	static int [] solution(int [][] intervals) {
		int len = intervals.length;
		// 这样做的 目的   不言而喻   为了 在  binarySearch 使用 排序  后的 数组 是 二分查找的 前提
		/**
		int nums [][] = intervals;
		System.out.println(nums == intervals);
		 
		 这样直接  把 引用 地址 赋值 给 nums  
		 这样的 话 两者  共同一个 地址 
		 */
		int nums [][] = new int [len][2];
		for(int i = 0 ; i < len ;i++) {
			/**
			 * 我还需要原先的 intervals  中的  原始值的  下标  
			 * 因为 返回的   ans 数组 中的 就是  原始 数组   中的  原始数据的 下标 
			 */
			nums[i][0] = intervals[i][0];
			// 对 数组中的 原始 index 进行 记录 
			nums[i][1] = i;			
		}
		// 这个 跟下面那个 是 等效的 
		Arrays.sort(nums,(a,b) -> a[0] - b[0]);
		for(int i [] : nums) {
			System.out.println(Arrays.toString(i));
		}
		
/**		Arrays.sort(nums,new Comparator<int []> () {

			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				
				return o1[0] - o2[0];
			}
			
		});*/
		int ans [] = new  int [len];
		for(int i = 0; i < len ;i++) {
			int target  = intervals[i][1];
			int temp = binarySearch(nums,target);
			ans [i] = temp; 
		}
//		System.out.println(binarySearch(nums,3));
		return ans;
	}
	static int binarySearch(int nums [][] ,int target) {
		int r = nums.length - 1;
		int l = 0;
		while(l < r) {
			int mid = l + (r - l >> 1);
			if(target == nums[mid][0])
				return nums[mid][1];
			else if(nums[mid][0] > target) {
				r = mid - 1;
			}
			else {
				l = mid + 1;
			}
		}
		return -1;
	}
}
